The present invention relates generally image reconstruction and more specifically to a process for reconstruction of digital images that takes advantage of information entropy properties.
Lossy image compression algorithms are currently used in order to minimize storage requirements and transmission bandwidth requirements for digital image data. “Lossy” compression schemes stand in contrast to “lossless” compression in that lossless compression yields a reconstructed image which is identical to the original image. Lossy compressions reinflate to an image which has some degradation. The advantages of lossy compression over lossless compression is that much higher compression fractions can be achieved with lossy schemes. Further, to the human eye, little or no loss can be perceived, which makes lossy compression adequate for may uses.
Current compression algorithms gain reductions in the amount of data storage required by taking advantage of redundant information in the original image. These redundancies can be in spatial or spectral domains, or in the time domain in video applications where multiple frames are being sent.
Examples of current image compression and reconstruction algorithms and systems are shown in the following U.S. Patents, the disclosures of which are incorporated herein by reference:
U.S. Pat. No. 6,054,943, Apr. 25, 2000, Multilevel digital information compression based on Lawrence algorithm, Lawrence, John Clifton,
U.S. Pat. No. 6,298,162, Oct. 2, 2001, Image compression/expansion using parallel decomposition/recomposition, Sutha, Surachai,
U.S. Pat. No. 6,259,819, Jul. 10, 2001, Efficient method of image compression comprising a low resolution image in the bit stream, Andrew, James Phillip,
U.S. Pat. No. 6,212,301, Apr. 3, 2001, Systems and methods for digital image compression, Warner, Scott J.
U.S. Pat. No. 6,243,420 B1, Mitchell et al; U.S. Pat. No. 6,222,884, Mitchell et al; U.S. Pat. No. 6,198,842 B1, Yeo et al. All of the patents are related and refer to methods to perform multi-spectral (i.e. multi color) image compression. The “new art” described in all three is the method to compress multiple color planes into a single plane. The actual compression of single plane images relies on methods not included in the patent. As described, the patents suggest using the JPEG standard. The maximum entropy method I describe is a method suitable for single color plane images, and could be used with these patents in place of the JPEG or GIF standards as the single plane image compressor.
U.S. Pat. No. 6,208,754 B1, Abe. The patent presents a device that combines three-color data into a single image pixel. The resulting single plane image is then expected to be compressed using an extant technique, such as JPEG compression. As is the case the Mitchell et al and Yeo et al patents, the maximum entropy method could be used in place of the JPEG compression with this device.
U.S. Pat. No. 6,295,379 B1, Goldstein et al. The method concentrates on a technique primarily for transmission of digital video. The image compression technique differs from the maximum entropy method of the present invention in that it concentrates on a line-by-line compression of images, where the present method compresses the entire image at once.
U.S. Pat. No. 6,201,614 B1, Lin. This patent is for a codebook method to compress dithered images relating gray scale levels in dithered images to a codebook entry. The present invention uses no codebooks, nor is it limited to dithered images.
U.S. Pat. No. 6,226,445 B1, Abe. The patent is for a device which allows JPEG compression (or any compression relying on discrete cosine transforms (DCTs)), and incorporates copy-protection properties and password protection into the ability to decompress the images. The maximum entropy method does not use DCTs.
U.S. Pat. No. 6,212,301 B1, Warner et al. The method presents a line-by-line image compression method, which allows for progressive/iterative improvement of the image as it is transmitted. The maximum entropy technique by contrast compresses the entire image at once, allowing for greater image compression than line-by-line methods are capable of.
U.S. Pat. No. 6,298,162 B1, Sutha et al. Compression method for massively parallel computers. Method assumes an image compression technique which uses subsampling of the images, which yields advantages for parallel computing in that each subsample can be acted on by a separate processor. The maximum entropy method described in the present invention does not subsample image pixels, and is not improved by using parallel computers.
The standard in lossy compression schemes for image data is the JPEG (Joint Photographic Experts Group) algorithm. This is an algorithm based on the Discrete Cosine Transform (DCT) and typically achieves compression ratios of 20:1. Other lossy techniques include wavelet transforms, vector quantization, and fractal compression. Wavelet transform compression algorithms are similar but make use of the discrete wavelet transform (DWT) rather than the DCT. The DWT tend to have improved compression properties over DCT schemes, allowing compression factors of 100:1 with fairly mild image degradation. Also, DWT schemes are more robust against transmission and decoding errors than DCT schemes. Vector quantization (VQ), is a technique which maps blocks of pixels (subsets of the image) to similar blocks defined in a “codebook” library. Typically compression ratios of ˜50:1 are achieved by this method. Fractal compression is a special case of VQ, where the codebook is virtual and made up of fractals from Iterated Functions Systems (IFS). These fractal subimages then map the various scales, from large to small, making up the entire image, the implementation of which is known as Partitioned Iterated Function Systems (PIFS). Fractal compression offered the possibility of 10,000:1 compression ratios, but was very costly (hundreds of hours) in computer time to encode. In practice, for non-contrived images, compression ratios from 4:1 to 100:1 have typically been achieved.